package algorithm.sort;

public class ShellSort {


    public static void main(String[] args) {
        // 希尔排序，基于插入排序，缩小增量排序，n/2,n/2/2 直到1的增量比较大小，让左边都是较小的元素
        // 从小到大排序
        System.out.println("======推导========");
        deductionShell();
        System.out.println("======准备数据========");
        int[] arr = TestHelp.random(10);
        TestHelp.print("比较前",arr);
        long begin = TestHelp.begin();
        shell(arr);
        TestHelp.end(begin);
        TestHelp.print("比较后",arr);

    }

    /**
     * 希尔排序 直接插入间隔是1，希尔间隔为n/2,递减到1
     * 时间复杂度O(n^2)-O(n^1.3)
     * 空间复杂度O(1)，只需要一个临时变量
     * 不稳定，相同元素的位置会变换，有不同步长间相同元素交换
     */
    public static void shell(int[] arr){
        int counter = 0;
        for (int step = arr.length/2; step >=1 ; step=step/2) {
            for (int i = step; i < arr.length; i++) {
                for (int k = i-step; k >=0 ; k=k-step) {
                    if(arr[k]>arr[k+step]){
                        TestHelp.swap(arr,k,k+step);
                    }
                }
            }
            counter++;
            TestHelp.print("第"+counter+"趟",arr);
        }
    }

    /**
     * 逐步推导，演绎，先从第二个元素，第三个元素。。一个个元素排序处理
     */
    public static void deductionShell(){
        int[] arr = new int[]{8,3,12,6,19,2,33,1,2,5};
        // 10/2 = 5,按5的增量（步长），增数据分成五组，（8,2）（3,33）（12,1）（6,2）（19,5），对五组数据分别进行直接插入排序，对于两个元素来说是比较大小，交换即可，但不是直接插入排序算法
        // 第一趟============ 10/2  步长为5的一次直接插入排序
        int step = 5;
        for (int i = step; i < arr.length; i++) {
            for (int k = i-step; k >=0 ; k=k-step) {
                if(arr[k]>arr[k+step]){
                    TestHelp.swap(arr,k,k+step);
                }
            }
        }
        TestHelp.print("第一趟",arr);// [2, 3, 1, 2, 5, 8, 33, 12, 6, 19]
        // 第二趟============ 10/2/2 = 2  ,(2,1,5,33,6)(3,2,8,12,19)=》先直接插入排序，即 （1,2,5,6,33)(2,3,8,12,19)
        step = 2;
        for (int i = step; i < arr.length; i++) {
            for (int k = i-step; k >=0 ; k=k-step) {
                if(arr[k]>arr[k+step]){
                    TestHelp.swap(arr,k,k+step);
                }
            }
        }
        TestHelp.print("第二趟",arr);
        // 第三趟============ 10/2/2/2 = 1
        step = 1;
        for (int i = step; i < arr.length; i++) {
            for (int k = i-step; k >=0 ; k=k-step) {
                if(arr[k]>arr[k+step]){
                    TestHelp.swap(arr,k,k+step);
                }
            }
        }
        TestHelp.print("第三趟",arr);

    }
}
